package leetcode.hot100;
import datastruct.tree.TreeNode;

public class Solution236 {

    TreeNode lowestCommonAncestor = null;

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        postOrder(root, p, q);
        return lowestCommonAncestor;
    }

    public boolean postOrder(TreeNode root, TreeNode p, TreeNode q){
        if(root==null) return false;
        //lowestCommonAncestor已找到，不用再递归
        if(lowestCommonAncestor!=null) return false;

        //本节点
        boolean midRes = root==p||root==q;

        //左子树查找
        boolean leftRes = postOrder(root.left,p,q);
        if(leftRes&&midRes){
            lowestCommonAncestor = root;
            return true; //不再对右子树遍历
        }

        //右子树查找
        boolean rightRes = postOrder(root.right,p,q);
        if(leftRes&&rightRes||rightRes&&midRes){
            lowestCommonAncestor = root;
        }

        //返回以root为根的树有无p,q
        return leftRes||rightRes||midRes;
    }

    //大神解法
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left==null) return right;
        if(right==null) return left;
        //left和right都非null
        return root;
    }
}
